package com.algrithom.tree.binarytree;

import java.util.Objects;

import com.common.model.TreeNode;
import com.util.TreeOperUtil;

/**
 * 1644. 二叉树的最近公共祖先 II
 *
 * @author think
 */
public class Solution3 {
    
    TreeNode<Integer> ans = null;
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{3,5,1,6,2,0,8,null,null,7,4};
        TreeNode<Integer> root = TreeOperUtil.createTree(array,0);
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.lowestCommonAncestor(root,5,1).getValue());
    }
    
    public TreeNode<Integer> lowestCommonAncestor(TreeNode<Integer> root,int p,int q){
        dfs(root,p,q);
        return ans;
    }
    
    private boolean dfs(TreeNode<Integer> root,int p,int q){
        if (Objects.isNull(root)) {
            return false;
        }
        boolean left = dfs(root.getLeftChild(),p,q);
        boolean right = dfs(root.getRightChild(),p,q);
        if ((left && right) || ((root.getValue().equals(p) || root.getValue().equals(q))) && (left || right)) {
            ans = root;
            return true;
        }
        return left || right || root.getValue().equals(q) || root.getValue().equals(p);
    }
}
